(1) Technical Field
The present invention relates to a recognition system and, more particularly, to a multi-dimensional pattern matching system for secure search and recognition.
(2) Description of Related Art
Pattern matching is fundamental to computer science. Pattern matching is typically a process by which a system searches files or other data in an attempt to recognize an item of interest by matching a pattern with a predetermined or otherwise recognizable pattern. Pattern matching is used in a wide range of applications, such as text-processing, image search, image recognition, database (DB) operations, networking and security applications. In most cases search patterns are one-dimensional. However, in several applications, especially image search and image recognition, the patterns and texts are naturally of higher dimensions (i.e., two or three dimensions). In such cases, traditional one-dimensional pattern matching algorithms and protocols are less efficient than multi-dimensional pattern matching algorithms.
Although multi-dimensional pattern matching algorithms exists (such as G. M. Landau and U. Vishkin, “Pattern matching in a digitized image” Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 453-462, 1992, and R. M. Karp, R. E. Miller and A. L. Rosenberg, “Rapid identification of repeated patterns in strings, trees and arrays,” Proc. 4th ACM Symposium on Theory of Computing, 125-136, 1972, and A. V. Aho and M. J. Corasick, “Efficient String Matching,” CACM, Vol. 18, No. 6, 333-340, 1975), there is not currently available any secure multi-dimensional pattern matching algorithms. By “secure”, it is meant that the pattern is not revealed to the party holding the text and nothing other than the result of the match is revealed to the party holding the pattern (text and pattern are multidimensional in this case. Thus, existing multi-dimensional pattern matching protocols are not “secure” because they do not provide the guarantees required above (i.e., the pattern is not revealed to the party holding the text and nothing other than the result of the match is revealed to the party holding the pattern).
Further, the computational cost of utilizing existing protocols is prohibitive. For example, multi-dimensional pattern matching can be generalized from single-dimensional secure pattern matching, where the pattern and the text are vectors. Example of single-dimensional protocols include those as described in Literature Reference Nos. 2, 5, 6, and 10 (See the List of Cited Literature References, Literature Reference Nos. 2, 5, 6, and 10). Even in the case where the pattern and text are vectors, the number of exponentiations and bandwidth is at best O((nm)d). Thus, as the dimension grows, the computational cost grows exponentially.
Other existing secure pattern matching techniques that depend on securely evaluating finite state machines (FSM) (see Literature Reference Nos. 2, 5, and 6) require a number of interaction rounds between a client and server that proportional to the number of states in the FSM. This significantly limits the size of the FSM that can be evaluated efficiently. It also renders the usage of wildcards problematic because they cause a quadratic explosion in the number of states.
As such, a continuing need exists for an efficient and secure multi-dimensional pattern matching without the dramatic computational costs of existing protocols.